package zuo.highLevel_6;

/**
 * @Author: Forx
 * @Data: 2021/7/10
 * @Desc: Algorithm - zuo.highLevel_6
 * @Version: v1.0
 */

import com.sun.org.apache.bcel.internal.generic.BREAKPOINT;
import tools.generRandomBuff.RandomBuff;

import java.util.Arrays;

/**
 * 给定一个数组arr,长度为N且每个值都是正数，代表N个人的体重。再给定一个正数
 * limit,代表一艘船的载重。以下是坐船规则，1)每艘船最多只能做两人；2)乘客
 * 的体重和不能超过limit。返回如果同时让这N个人过河最少需要几条船。
 *
 * 排序后首位相接
 * */
class MinBoats{
    public int method1(int[] arr,int limit){
        Arrays.sort(arr);
        int left = 0;
        int right = arr.length-1;
        int ans = 0;
        while (left<right){
            if(arr[left] + arr[right] <=limit){
                ans++;
                left++;
                right++;
            }else {
                ans++;
                right--;
            }
        }
        return ans;
    }

    public int method2(int[] arr,int limit){
        Arrays.sort(arr);
        int halfLimit = (int) Math.floor((double)limit/2);
        int halfIndex = -1;
        for (int i = arr.length-1; i >= 0; i--) {
            if(arr[i] <=halfIndex){
                halfIndex = i;
                break;
            }
        }
        if(halfIndex==-1){
            return arr.length;
        }
        if(halfIndex==arr.length-1){
            return (int)Math.ceil((double)arr.length/2);
        }
        int left = halfIndex;
        int right = halfIndex+1;
        int ans = 0;
        int ansDouble = 0;
        while (left>=0 && right < arr.length-1){
            if(arr[left] + arr[right] <=limit){
                left--;
                right++;
                ans++;
            }else if(arr[left] + arr[right] > limit){
                left--;
                ansDouble++;
            }
        }
        if(left>=0){
            ans += Math.ceil((double) left/2);
        }
        if(right < arr.length-1){
            ans += arr.length-right;
        }
        ans+=Math.ceil((double)ansDouble/2);
        return ans;
    }
    public void test(){
        /**只有方法2是正确的*/
        int testTimes = 1000;
        for (int i = 0; i < testTimes; i++) {
            int min = 0;
            int max = 100;
            int maxSize = 100;
            int size = (int) (Math.random()*maxSize);
            int[] buff = RandomBuff.generateRandomBuff(max,size);
            System.out.println(Arrays.toString(buff));
            int ans1 =method1(buff,max);
            int ans2 =method2(buff,max);
            if(ans1==ans2){
                System.out.println("i = " + i + " OK");
            }else {
                System.out.println(Arrays.toString(buff));
                System.out.println("ERROR");
                System.out.println("ans1 = " + ans1);
                System.out.println("ans2 = " + ans2);
                break;
            }

        }
    }

}
/**
 *
 * 给定一个字符串,求出最长回文子序列
 *
 * 1.获得字符串的逆序列,寻找原序列和逆序列的最长公共子序列即为所求
 *  HL5中有讲
 * 2.
 * */

/**
 * 给定一个字符串,求出能使其变成回文串所需要插入的最少字符
 *
 * */

/**
 * 给定一个字符串str,返回把str全部切成回文子串的最小分割数。
 * 【举例】
 * str="ABA"。
 * 不需要切割，str本身就是回文串，所以返回0。
 * str="ACDCDCDAD"。
 * 最少需要切2次变成3个回文子串，比如"A"、"CDCDC"和"DAD",所以返回2。
 * */
/**
 * 对于一个字符串，从前开始读和从后开始读是一样的，我们就称这个字符串是回文串。例如"ABCBA","AA","A"
 * 是回文串，而"ABCD","AAB"不是回文串。牛牛特别喜欢回文串，他手中有一个字符串s,牛牛在思考能否从字
 * 符串中移除部分（0个或多个）字符使其变为回文串，并且牛牛认为空串不是回文串。牛牛发现移除的方案可能有
 * 很多种，希望你来帮他计算一下一共有多少种移除方案可以使s变为回文串。对于两种移除方案，如果移除的字
 * 符依次构成的序列不一样就是不同的方案。
 * 例如，XXY4种ABA5种
 * 【说明】
 * 这是今年的原题，提供的说明和例子都很让人费解。现在根据当时题目的所有测试用例，重新解释当时的题目
 * 含义：
 * 1)"1AB23CD21",你可以选择删除A、B、C、D,然后剩下子序列{1,2,3,2,1},只要剩下的子序列是同一个，那
 * 么就只算1种方法，和A、B、C、D选择什么样的删除顺序没有关系。
 * 2)"121A1",其中有两个{1,2,1}的子序列，第一个{1,2,1}是由{位置0,位置1,位置2}构成，第二个{1,2,1}
 * 是由（位置0,位置1,位置4)构成。这两个子序列被认为是不同的子序列。也就是说在本题中，认为字面值一样
 * 但是位置不同的字符就是不同的。
 * 3)其实这道题是想求，str中有多少个不同的子序列，每一种子序列只对应一种删除方法，那就是把多余的东
 * 西去掉，而和去掉的顺序无关。
 * 4)也许你觉得我的解释很荒缪，但真的是这样，不然解释不了为什么，XXY4种ABA5种，而且其他的测
 * 试用例都印证了这一点。
 *
 * */

public class HL6 {
    public static void main(String[] args) {
        new MinBoats().test();
    }
}
